class Matrix:
    '''封装矩阵乘法'''
    MOD_NUM = 10**9 + 7

    def __init__(self, value) -> None:
        self.v: list = value 
    
    def mul(self, obj):
        # 两个矩阵维度分别是(a,b), (b,c)
        obj: Matrix = obj
        a, b, c = len(self.v), len(self.v[0]), len(obj.v[0])
        
        matrix = [[0] * c for i in range(a)]  # 乘积维度：(a,c)
        r = Matrix(matrix)
        for i in range(a):
            for j in range(c):
                for k in range(b):
                    r.v[i][j] = (r.v[i][j] + self.v[i][k] * obj.v[k][j]) % self.MOD_NUM
        return r


def mi(A: Matrix, n: int) -> Matrix:
    '''求矩阵A的n次幂'''
    if n == 1:
        return A
    if n % 2 == 1:
        return mi(A, n-1).mul(A)
    else:
        t = mi(A, n // 2)
        return t.mul(t)

def method(n, k):
    '''求解一个测试用例'''
    if n == 1:
        return k 
    elif n > 1:
        A = Matrix([[k, -1], [1, 0]])
        F = Matrix([[k], [2]])  # f(0)=2, f(1)=k
        R = mi(A, n-1).mul(F)
        return R.v[0][0]

if __name__ == '__main__':
    m = int(input())
    for _ in range(m):
        n, k = map(int, input().split(' '))  # 以前我总用列表推导式
        print(method(n, k))
